Coefficient binomial de Gauss
En mathématiques, les coefficients binomiaux de Gauss ou coefficients q-binomiaux ou encore q-polynômes de Gauss sont des q -analogues des coefficients binomiaux, introduits par C. F. Gauss en 1808 [1].
Le coefficient q-binomial, écrit ou , est un polynôme en à coefficients entiers, qui donne, lorsque est une puissance de nombre premier, le nombre de sous-espaces vectoriels de dimension d'un espace vectoriel de dimension sur un corps fini à éléments.
Définition algébrique
[modifier | modifier le code]Les coefficients binomiaux de Gauss sont définis pour et entiers naturels et différent de 1 par[2] :
Pour , la valeur est 1 car le numérateur et le dénominateur sont tous deux des produits vides.
Bien que la première formule semble donner une fonction rationnelle en , elle désigne en fait un polynôme en de degré (la division est exacte dans ).
Tous les facteurs au numérateur et au dénominateur sont divisibles par , avec comme quotient le q-analogue :
- .
La division de ces facteurs donne la formule équivalente :
ce qui met en évidence le fait que la substitution dans donne le coefficient binomial ordinaire
En termes de q-factorielles , la formule peut être écrite comme suit :
- ,
forme compacte (souvent donnée comme première définition), qui cache cependant la présence de facteurs communs au numérateur et au dénominateur.
Cette forme rend évidente la symétrie pour .
Contrairement au coefficient binomial ordinaire, le coefficient binomial de Gauss a une limite finie quand , pour :
- .
Exemples
[modifier | modifier le code]La plupart des logiciels de calcul formel ont des fonctions pour calculer les q-binomiaux, par exemple :
- q_binomial(n, k) dans SageMath ;
- QBinomial(n,k,q) dans Maple (avec le package QDifferenceEquations) ;
- QBinomial[n,k,q] dans Mathematica.
Relations de récurrence
[modifier | modifier le code]Avec les définitions ci-dessus, on montre :
- ,
Cette égalité est la q-analogue de la formule du pion pour les coefficients binomiaux classiques.
Avec la formule , on déduit les relations q-analogues de la relation de Pascal :
et
- .
Ces relations montrent, par récurrence, que les coefficients q-binomiaux sont bien des polynômes à coefficients entiers en .
q-analogue du triangle de Pascal
[modifier | modifier le code]Le triangle des coefficients binomiaux de Gauss, q-analogue du triangle de Pascal, se construit grâce aux relations précédentes :
1 | |||||||||||||||||
1 | 1 | ||||||||||||||||
1 | 1+q | 1 | |||||||||||||||
1 | 1+q+q2 | 1+q+q2 | 1 | ||||||||||||||
1 | 1+q+q2+q3 | 1+q+2q2+q3+q4 | 1+q+q2+q3 | 1 | |||||||||||||
Pour q =2, il forme la suite A022166 de l'OEIS ; pour les entiers q suivants jusqu'à 24, les numéros des références se succèdent de 1 en 1 ; pour q=-2 : suite A015109 de l'OEIS et suivantes jusqu'à q=-24.
Autres références de l'OEIS concernant le q-triangle de Pascal :
- suite A008967 de l'OEIS et suite A219237 de l'OEIS donnant la succession des coefficients des polynômes des colonnes 2 et 4 : et .
- suite A083906 de l'OEIS donnant les coefficients de la somme de chaque ligne.
- suite A089789 de l'OEIS donnant le nombre de facteurs irréductibles de .
Définitions combinatoires
[modifier | modifier le code]Nombre de combinaisons présentant un nombre d'inversions donné
[modifier | modifier le code]Le coefficient binomial ordinaire compte les k-combinaisons obtenues à partir de éléments. Si l'on prend ces éléments comme les différentes positions de caractères dans un mot de longueur , alors chaque k-combinaison correspond à un mot de longueur utilisant un alphabet de deux lettres, disons {0,1}, avec copies de la lettre 0 (indiquant les positions dans la combinaison choisie) et lettres 1 (pour les positions restantes).
Pour obtenir de ce modèle le coefficient binomial de Gauss , il suffit de compter chaque mot avec un facteur , où est le nombre d' "inversions" du mot : le nombre de paires de positions pour lesquelles la position la plus à gauche de la paire contient une lettre 1 et la position la plus à droite contient une lettre 0 dans le mot.
Par exemple, pour , 0011 ne présente pas d'inversion, 0101 en présente une (en positions 2 et 3), 0110 et 1001 en présentent deux, 1010 en présente trois et 1100 en présente quatre. Cela correspond aux coefficients du polynôme en :
D'une façon générale, si est le nombre de mots binaires de lettres, contenant lettres 0, et présentant inversions, on a :
- .
On démontre ceci à partir de la relation .
Une façon visuelle de comprendre cette définition consiste à associer à chaque mot un chemin à travers une grille rectangulaire de côtés de hauteur et de largeur , du coin inférieur gauche au coin supérieur droit, en faisant un pas à droite pour chaque lettre 0 et un pas vers le haut pour chaque lettre 1. Le nombre d'inversions du mot est alors égal à l'aire de la partie du rectangle qui se trouve sous le chemin.
Dénombrements de rangements de boules dans des urnes ou de partitions d'entiers
[modifier | modifier le code]Soit le nombre de façons de lancer boules dans urnes indiscernables pouvant contenir boules au plus, .
Pour , est donc aussi le nombre de partitions de l'entier en parties au plus, chacune des parties étant inférieure ou égale à .
On montre qu'avec les notations précédentes, .
Donc où désigne le coefficient de dans le polynôme .
Notons que par symétrie, .
Nombre de sous-espaces vectoriels d'un espace vectoriel fini
[modifier | modifier le code]Lorsque est une puissance de nombre premier, le nombre de sous-espaces vectoriels de dimension d'un espace vectoriel de dimension sur un corps fini à éléments est [3].
Donc le nombre de sous-espaces projectifs de dimension d'un espace projectif de dimension sur un corps fini à éléments est .
Parties à k éléments de {1,2,..,n}
[modifier | modifier le code]Posons et pour une partie , notons sa somme ; alors[4]:
- .
q-analogue de la formule du binôme
[modifier | modifier le code]Pour a et b réels ou complexes, on montre la formule q-analogue de la formule du binôme :
- , dénommée « formule du binôme de Gauss »[4] .
On en déduit, pour , le développement du produit infini : (première identité d'Euler).
Par exemple, pour , , on obtient , voir suite A081845 de l'OEIS.
Il existe aussi une formule q-analogue de la formule du binôme négatif, dénommée « formule du binôme de Heine »[4] :
- pour .
dont on déduit :
- pour et (deuxième identité d'Euler).
Par exemple, pour , on obtient , voir suite A065446 de l'OEIS.
Autres relations entre coefficients q-binomiaux
[modifier | modifier le code]q-analogue de la sommation en colonne
[modifier | modifier le code]Par application du q-analogue de relation de Pascal, on obtient le q-analogue de la formule d'itération de Pascal[1] :
q-analogue de l'identité de Vandermonde
[modifier | modifier le code]Le q-analogue de l'identité de Vandermonde est[4]
- .
Sommation alternée d'une ligne
[modifier | modifier le code]Pour une ligne paire[1] :
Pour une ligne impaire (évident par la propriété de symétrie)[1] :
Étoile de David
[modifier | modifier le code]D'après leur définition algébrique, les coefficients binomiaux de Gauss vérifient le théorème de l'étoile de David, deuxième énoncé.
Voir aussi
[modifier | modifier le code]Références
[modifier | modifier le code]- (la) C. F. Gauss, Opera, Vol. 2, Summatio quarumdam serierum singularium, (} lire en ligne), p. 7–12, paragraphes 5 à 9
- (en) George Pólya et Gábor Szegő, Problems and Theorems in Analysis, vol. I, Springer, (1re éd. 1972) (lire en ligne), p. 11 à 13
- (en) M. Sved, « ,Gaussians and binomials », Ars Combinatoria, 17A, , p. 325-351. (lire en ligne)
- (en) Victor Kac et Pokman Cheung, Quantum Calculus, Springer, (lire en ligne), chapitre 5, th. 7.6, th. 6.1
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Gaussian binomial coefficient » (voir la liste des auteurs).